package org.example.game.history;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/06/02 11:24
 */
public class Solution100322 {

    public static void main(String[] args) {
        Solution100322 solution100322 = new Solution100322();
        System.out.println(solution100322.clearStars("a*a*b*a*"));
    }

    public String clearStars(String s) {
        if(!s.contains("*")){
            return s;
        }

        if(s.replaceAll("\\*", "").length() == s.length() /2){
            return "";
        }

        HashMap<Character, List<Integer>> characterListHashMap = new HashMap<>();
        int index = 0;
        int lastIndex= s.lastIndexOf("*");
        char[] chars = s.toCharArray();
        for(Character c : s.toCharArray()){
            if(c.equals('*')){
                //剔除一个字母
                int last = getLastIndex(characterListHashMap);
                //替换位置
                chars[last] = '0';
                chars[index] = '0';
            }else {
                //记录一个字母
                characterListHashMap.putIfAbsent(c, new ArrayList<>());
                characterListHashMap.get(c).add(index);
            }
            index++;
            if(index > lastIndex){
                break;
            }
        }
        //还原字符串
        return String.valueOf(chars).replaceAll("0", "");
    }

    private int getLastIndex(HashMap<Character, List<Integer>> characterListHashMap) {
        Object[] characters = characterListHashMap.keySet().toArray();
        Arrays.sort(characters);
        for (Object c : characters) {
            if(characterListHashMap.containsKey(c) && characterListHashMap.get(c).size() > 0){
                Integer lastIndex = characterListHashMap.get(c).get(characterListHashMap.get(c).size() - 1);
                characterListHashMap.get(c).remove(lastIndex);
                return lastIndex;
            }
        }
        return -1;
    }
}
